#pragma once
#include <limits>
#include <math.h>
#include <list>
#include "../tools/Util.h"
using std::list;


//a few useful constants
const int     MaxInt    = (std::numeric_limits<int>::max)();
const double  MaxDouble = (std::numeric_limits<double>::max)();
const double  MinDouble = (std::numeric_limits<double>::min)();
const float   MaxFloat  = (std::numeric_limits<float>::max)();
const float   MinFloat  = (std::numeric_limits<float>::min)();


const float   PI			= 3.141592653589732f;
const float   TWOPI			= PI * 2;
const float   HALFPI		= PI / 2;
const float	  THREEHALFPI	= 3 * HALFPI;
const float   QUARTERPI		= PI / 4;
const float	  EIGTHPI		= PI / 8;

struct vector2D;

typedef struct tagRECTF
{
	float    left;
	float    top;
	float    right;
	float    bottom;

   tagRECTF() {}
  
   tagRECTF(float L, float T, float R, float B)
   {
      left = L;
      top = T;
      right = R;
      bottom = B;
   }
	//RECT & operator=(tagRECTF & rect, RECT & r);

} RECTF;

// Create a Hexagon structure (using the pointy format)
typedef struct tagHEX
{
   float left,             //lowest X value
         top,              //lowest Y value
         topMiddle,        //Y value for upper corners
         bottomMiddle,     //Y value for lower corners
         right,            //Highest X value
         bottom;           //Highest Y value

   float centerX,
         centerY;

   tagHEX() {}

   tagHEX(float centerX, float centerY, float side)
   {
      float a = sqrt((side * side) - ((side / 2) * (side / 2)));

      this->centerX = centerX;
      this->centerY = centerY;
      this->top = centerY - side;
      this->topMiddle = centerY - (side / 2);
      this->bottom = centerY + side;
      this->bottomMiddle = centerY + (side / 2);
      this->left = centerX - a;
      this->right = centerX + a;
   }

} HEX_SHAPE;


//	Define vector	-	used for movement or calculations
struct vector2D
{
	float fX;
	float fY;

	vector2D() : fX(0.0f), fY(0.0f)
	{
	}

	vector2D(float x, float y) : fX(x), fY(y)
	{
	}

	vector2D operator+(const vector2D& v)
	{
		return vector2D(fX + v.fX, fY + v.fY);
	}

	vector2D operator-(const vector2D& v)
	{
		return vector2D(fX - v.fX, fY - v.fY);
	}

	vector2D operator*(const float f)
	{
		return vector2D(fX * f, fY * f);
	}

	vector2D operator/(const float f )
	{
		return vector2D(fX / f, fY / f);
	}

	vector2D operator+(const vector2D& v) const
	{
		return vector2D(fX + v.fX, fY + v.fY);
	}

	vector2D operator-(const vector2D& v) const
	{
		return vector2D(fX - v.fX, fY - v.fY);
	}

	vector2D operator*(const float f) const
	{
		return vector2D(fX * f, fY * f);
	}

	vector2D operator/(const float f ) const
	{
		return vector2D(fX / f, fY / f);
	}

	bool operator!=(const vector2D & v) const
	{
		return fX != v.fX && fY != v.fY;
	}

	bool operator==(const vector2D & v) const
	{
		return fX == v.fX && fY == v.fY;
	}

	vector2D operator+=(const vector2D& v)
	{
		(*this).fX =  fX + v.fX;
		(*this).fY =  fY + v.fY;
		return *this;
	}

	vector2D operator-=(const vector2D& v)
	{
		(*this).fX = fX - v.fX;
		(*this).fY = fY - v.fY;
		return *this;
	}

	vector2D operator*=(const float f)
	{
		(*this).fX = fX * f;
		(*this).fY = fY * f;
		return *this;
	}

	vector2D operator/=(const float f )
	{
		(*this).fX = fX / f;
		(*this).fY = fY / f;
		return *this;
	}

	vector2D Perp()const
	{
		return vector2D(-fY, fX);
	}

	void Zero()
	{
		fX = 0.0f;
		fY = 0.0f;
	}

	float Dot(vector2D vect)
	{
		return (fX * vect.fX) + (fY * vect.fY);
	}

	float Length()
	{
		return sqrt((fX * fX) + (fY * fY));
	}

	float LengthSq()
	{
		return (fX * fX) + (fY * fY);
	}

	void Truncate(float max)
	{
		if (this->Length() > max)
		{
			this->Normalize();

			*this = (*this) * max;
		} 
	}

	void Normalize()
	{
		float vector_length = this->Length();

		if (vector_length > std::numeric_limits<float>::epsilon())
		{
			this->fX = fX / vector_length;
			this->fY = fY / vector_length;
		}
	}
};

vector2D MidPoint(vector2D v1, vector2D v2);
//	Find the length of a vector (magnitude)
float Vector2DLength(vector2D vec);

// Find the dot product
float DotProduct(vector2D v1, vector2D v2);

//	Normalize a vector
vector2D Vector2DNormalize(vector2D vec);

//	Rotate a vector
/*
X, Y	=	[X]
[Y]
[1]

[	cos&	sin&	0	]		[X]		[X1]
[  -sin&	cos&	0	]	*	[Y]	=	[Y1]
[	0		0		1	]		[1]		[1]
*/
vector2D Vector2DRotate(vector2D vec, float fRadians);

inline float Vector2DDistance(const vector2D &v1, const vector2D &v2)
{

	float ySeparation = v2.fY - v1.fY;
	float xSeparation = v2.fX - v1.fX;

	return sqrt(ySeparation*ySeparation + xSeparation*xSeparation);
}

inline float Vector2DDistanceSq(const vector2D &v1, const vector2D &v2)
{

	float ySeparation = v2.fY - v1.fY;
	float xSeparation = v2.fX - v1.fX;

	return ySeparation*ySeparation + xSeparation*xSeparation;
}
//	Find the angle between 2 vectors
/*
a . b = (||a|| ||b||) cos @

cos @ = (a . b) / (||a|| ||b||)

@ = arccos (a.b)  
*/

typedef struct tagTRI
{
   vector2D point1;
   vector2D point2;
   vector2D point3;
   
   tagTRI() {}
   
   tagTRI(vector2D p1, vector2D p2, vector2D p3)
   {
      point1 = p1;
      point2 = p2;
      point3 = p3;
   }

} TRI_SHAPE;


float AngleBetweenVectors(vector2D v1, vector2D v2);

//	Linear Interpolation
//	v = a + ((b - a) * t)
//float Lerp(float fStart, float fEnd, float fPercent);

//	Tests if two floats are approximately equal given a margin of error
bool FloatEquals(float fResult, float fExpected, float fEpsilon = 0.001f);

// Converts Seconds to hours and minutes
void SecondsToStandard(unsigned int nSecondsToConvert, int & nHours, int & nMins, int & nSecs);

//	Determines which way to turn (counter clockwise (+) or clockwise (-))
float Steering(vector2D vOrientation, vector2D vToTarget);


//	Linear Interpolation
//	v = a + ((b - a) * t)
template <typename T>
T Lerp(T fStart, T fEnd, float fPercent)
{
	return fStart + (static_cast<T>((fEnd - fStart) * fPercent));
}

DWORD LerpColor(DWORD startColor, DWORD endColor, float percent);

template <typename T>
T Interpoloate(T start, T end, float current, float max)
{
	return start * ((max - current) / max) + end * current / max;
}

template <typename T>
T Max(T a, T b)
{
	if(a > b)
		return a;
	else
		return b;
}

template <typename T>
T Min(T a, T b)
{
	if(a < b)
		return a;
	else 
		return b;
}

template <typename T>
T Clamp(T value, T min, T max)
{
	if(value < min)
		value = min;
	else if(value > max)
		value = max;

	return value;
}

bool BitOn(unsigned int & value, unsigned int flag);
void TurnBitOn(unsigned int & value, unsigned int flag);
void TurnBitOff(unsigned int & value, unsigned int flag);
void ToggleBit(unsigned int & value, unsigned int flag);

bool PointInTriangle(float x, float y, TRI_SHAPE & tri);
bool PointInRect(int x, int y, RECT & rect);
bool PointInRect(float x, float y, RECTF & rect);
bool PointInCircle(int x, int y, int centerX, int centerY, int radius);
bool PointInCircle(float x, float y, float centerX, float centerY, float radius);
bool PointInHexagon(float x, float y, HEX_SHAPE & hex);

RECT ScreenPercentsToRect(float left, float top, float width, float height);


float RandomFloat(float min, float max);

int RandomInt(int min, int max);

bool CheckCircleCollision(vector2D& vA, double radA, vector2D& vB, double radB);

//----------------------- TagNeighbors ----------------------------------
//
//  tags any entities contained in a std container that are within the
//  radius of the single entity parameter
//------------------------------------------------------------------------
template <class T, class conT>
void TagNeighbors(const T& entity, conT& ContainerOfEntities, double radius)
{
	//iterate through all entities checking for range
	for (typename conT::iterator curEntity = ContainerOfEntities.begin();
		curEntity != ContainerOfEntities.end();
		++curEntity)
	{
		//first clear any current tag
		(*curEntity)->UnTag();

		vector2D to = (*curEntity)->GetCenter() - entity->GetCenter();

		//the bounding radius of the other is taken into account by adding it 
		//to the range
		double range = radius + (*curEntity)->GetBoundingRadius();

		//if entity within range, tag for further consideration. (working in
		//distance-squared space to avoid sqrts)
		if ( ((*curEntity) != entity) && (to.LengthSq() < range*range))
		{
			(*curEntity)->Tag();
		}

	}//next entity
}






//------------------------------------------------------------------------
//
//  Name:   C2DMatrix.h
//
//  Author: Mat Buckland 2002
//
//  Desc:   2D Matrix class 
//
//------------------------------------------------------------------------



class C2DMatrix
{
private:

	struct Matrix
	{

		float _11, _12, _13;
		float _21, _22, _23;
		float  _31, _32, _33;

		Matrix()
		{
			_11=0.0f; _12=0.0f; _13=0.0f;
			_21=0.0f; _22=0.0f; _23=0.0f;
			_31=0.0f; _32=0.0f; _33=0.0f;
		}

	};

	Matrix m_Matrix;

	//multiplies m_Matrix with mIn
	inline void  MatrixMultiply(Matrix &mIn);


public:

	C2DMatrix()
	{
		//initialize the matrix to an identity matrix
		Identity();
	}

	//create an identity matrix
	inline void Identity();

	//create a transformation matrix
	inline void Translate(float x, float y);

	//create a scale matrix
	inline void Scale(float xScale, float yScale);

	//create a rotation matrix
	inline void  Rotate(float rotation);

	//create a rotation matrix from a fwd and side 2D vector
	inline void  Rotate(const vector2D &fwd, const vector2D &side);

	//applys a transformation matrix to a std::vector of points
	inline void TransformVector2Ds(std::vector<vector2D> &vPoints);

	//applys a transformation matrix to a point
	inline void TransformVector2Ds(vector2D &vPoint);

	//accessors to the matrix elements
	void _11(float val){m_Matrix._11 = val;}
	void _12(float val){m_Matrix._12 = val;}
	void _13(float val){m_Matrix._13 = val;}

	void _21(float val){m_Matrix._21 = val;}
	void _22(float val){m_Matrix._22 = val;}
	void _23(float val){m_Matrix._23 = val;}

	void _31(float val){m_Matrix._31 = val;}
	void _32(float val){m_Matrix._32 = val;}
	void _33(float val){m_Matrix._33 = val;}

};



//multiply two matrices together
inline void C2DMatrix::MatrixMultiply(Matrix &mIn)
{
	C2DMatrix::Matrix mat_temp;

	//first row
	mat_temp._11 = (m_Matrix._11*mIn._11) + (m_Matrix._12*mIn._21) + (m_Matrix._13*mIn._31);
	mat_temp._12 = (m_Matrix._11*mIn._12) + (m_Matrix._12*mIn._22) + (m_Matrix._13*mIn._32);
	mat_temp._13 = (m_Matrix._11*mIn._13) + (m_Matrix._12*mIn._23) + (m_Matrix._13*mIn._33);

	//second
	mat_temp._21 = (m_Matrix._21*mIn._11) + (m_Matrix._22*mIn._21) + (m_Matrix._23*mIn._31);
	mat_temp._22 = (m_Matrix._21*mIn._12) + (m_Matrix._22*mIn._22) + (m_Matrix._23*mIn._32);
	mat_temp._23 = (m_Matrix._21*mIn._13) + (m_Matrix._22*mIn._23) + (m_Matrix._23*mIn._33);

	//third
	mat_temp._31 = (m_Matrix._31*mIn._11) + (m_Matrix._32*mIn._21) + (m_Matrix._33*mIn._31);
	mat_temp._32 = (m_Matrix._31*mIn._12) + (m_Matrix._32*mIn._22) + (m_Matrix._33*mIn._32);
	mat_temp._33 = (m_Matrix._31*mIn._13) + (m_Matrix._32*mIn._23) + (m_Matrix._33*mIn._33);

	m_Matrix = mat_temp;
}

//applies a 2D transformation matrix to a std::vector of Vector2Ds
inline void C2DMatrix::TransformVector2Ds(std::vector<vector2D> &vPoint)
{
	for (unsigned int i=0; i<vPoint.size(); ++i)
	{
		float tempX =(m_Matrix._11*vPoint[i].fX) + (m_Matrix._21*vPoint[i].fY) + (m_Matrix._31);

		float tempY = (m_Matrix._12*vPoint[i].fX) + (m_Matrix._22*vPoint[i].fY) + (m_Matrix._32);

		vPoint[i].fX = tempX;

		vPoint[i].fY = tempY;

	}
}

//applies a 2D transformation matrix to a single Vector2D
inline void C2DMatrix::TransformVector2Ds(vector2D &vPoint)
{

	float tempX =(m_Matrix._11*vPoint.fX) + (m_Matrix._21*vPoint.fY) + (m_Matrix._31);

	float tempY = (m_Matrix._12*vPoint.fX) + (m_Matrix._22*vPoint.fY) + (m_Matrix._32);

	vPoint.fX = tempX;

	vPoint.fY = tempY;
}



//create an identity matrix
inline void C2DMatrix::Identity()
{
	m_Matrix._11 = 1; m_Matrix._12 = 0; m_Matrix._13 = 0;

	m_Matrix._21 = 0; m_Matrix._22 = 1; m_Matrix._23 = 0;

	m_Matrix._31 = 0; m_Matrix._32 = 0; m_Matrix._33 = 1;

}

//create a transformation matrix
inline void C2DMatrix::Translate(float x, float y)
{
	Matrix mat;

	mat._11 = 1; mat._12 = 0; mat._13 = 0;

	mat._21 = 0; mat._22 = 1; mat._23 = 0;

	mat._31 = x;    mat._32 = y;    mat._33 = 1;

	//and multiply
	MatrixMultiply(mat);
}

//create a scale matrix
inline void C2DMatrix::Scale(float xScale, float yScale)
{
	C2DMatrix::Matrix mat;

	mat._11 = xScale; mat._12 = 0; mat._13 = 0;

	mat._21 = 0; mat._22 = yScale; mat._23 = 0;

	mat._31 = 0; mat._32 = 0; mat._33 = 1;

	//and multiply
	MatrixMultiply(mat);
}


//create a rotation matrix
inline void C2DMatrix::Rotate(float rot)
{
	C2DMatrix::Matrix mat;

	float Sin = sin(rot);
	float Cos = cos(rot);

	mat._11 = Cos;  mat._12 = Sin; mat._13 = 0;

	mat._21 = -Sin; mat._22 = Cos; mat._23 = 0;

	mat._31 = 0; mat._32 = 0;mat._33 = 1;

	//and multiply
	MatrixMultiply(mat);
}


//create a rotation matrix from a 2D vector
inline void C2DMatrix::Rotate(const vector2D &fwd, const vector2D &side)
{
	C2DMatrix::Matrix mat;

	mat._11 = fwd.fX;  mat._12 = fwd.fY; mat._13 = 0;

	mat._21 = side.fX; mat._22 = side.fY; mat._23 = 0;

	mat._31 = 0; mat._32 = 0;mat._33 = 1;

	//and multiply
	MatrixMultiply(mat);
}



//--------------------- PointToLocalSpace --------------------------------
//
//------------------------------------------------------------------------
inline vector2D PointToLocalSpace(const vector2D &point,
								  vector2D &AgentHeading,
								  vector2D &AgentSide,
								  vector2D &AgentPosition)
{

	//make a copy of the point
	vector2D TransPoint = point;

	//create a transformation matrix
	C2DMatrix matTransform;

	float Tx = -AgentPosition.Dot(AgentHeading);
	float Ty = -AgentPosition.Dot(AgentSide);

	//create the transformation matrix
	matTransform._11(AgentHeading.fX); matTransform._12(AgentSide.fX);
	matTransform._21(AgentHeading.fY); matTransform._22(AgentSide.fY);
	matTransform._31(Tx);           matTransform._32(Ty);

	//now transform the vertices
	matTransform.TransformVector2Ds(TransPoint);

	return TransPoint;
}


//--------------------- VectorToWorldSpace --------------------------------
//
//  Transforms a vector from the agent's local space into world space
//------------------------------------------------------------------------
inline vector2D VectorToWorldSpace(const vector2D &vec,
								   const vector2D &AgentHeading,
								   const vector2D &AgentSide)
{
	//make a copy of the point
	vector2D TransVec = vec;

	//create a transformation matrix
	C2DMatrix matTransform;

	//rotate
	matTransform.Rotate(AgentHeading, AgentSide);

	//now transform the vertices
	matTransform.TransformVector2Ds(TransVec);

	return TransVec;
}

//--------------------------- WorldTransform -----------------------------
//
//  given a std::vector of 2D vectors, a position and  orientation
//  this function transforms the 2D vectors into the object's world space
//------------------------------------------------------------------------
inline std::vector<vector2D> WorldTransform(std::vector<vector2D> &points,
											const vector2D   &pos,
											const vector2D   &forward,
											const vector2D   &side)
{
	//copy the original vertices into the buffer about to be transformed
	std::vector<vector2D> TranVector2Ds = points;

	//create a transformation matrix
	C2DMatrix matTransform;

	//rotate
	matTransform.Rotate(forward, side);

	//and translate
	matTransform.Translate(pos.fX, pos.fY);

	//now transform the object's vertices
	matTransform.TransformVector2Ds(TranVector2Ds);

	return TranVector2Ds;
}






//------------------------- DistToLineSegment ----------------------------
//
//  given a line segment AB and a point P, this function calculates the 
//  perpendicular distance between them
//------------------------------------------------------------------------
inline float DistToLineSegment(vector2D A,
							   vector2D B,
							   vector2D P)
{
	//if the angle is obtuse between PA and AB is obtuse then the closest
	//vertex must be A
	float dotA = (P.fX - A.fX)*(B.fX - A.fX) + (P.fY - A.fY)*(B.fY - A.fY);

	if (dotA <= 0) return Vector2DDistance(A, P);

	//if the angle is obtuse between PB and AB is obtuse then the closest
	//vertex must be B
	float dotB = (P.fX - B.fX)*(A.fX - B.fX) + (P.fY - B.fY)*(A.fY - B.fY);

	if (dotB <= 0) return Vector2DDistance(B, P);

	//calculate the point along AB that is the closest to P
	vector2D Point = A + ((B - A) * dotA)/(dotA + dotB);

	//calculate the distance P-Point
	return Vector2DDistance(P,Point);
}

//------------------------- DistToLineSegmentSq ----------------------------
//
//  as above, but avoiding sqrt
//------------------------------------------------------------------------
inline float DistToLineSegmentSq(vector2D A,
								 vector2D B,
								 vector2D P)
{
	//if the angle is obtuse between PA and AB is obtuse then the closest
	//vertex must be A
	float dotA = (P.fX - A.fX)*(B.fX - A.fX) + (P.fY - A.fY)*(B.fY - A.fY);

	if (dotA <= 0) return Vector2DDistanceSq(A, P);

	//if the angle is obtuse between PB and AB is obtuse then the closest
	//vertex must be B
	float dotB = (P.fX - B.fX)*(A.fX - B.fX) + (P.fY - B.fY)*(A.fY - B.fY);

	if (dotB <= 0) return Vector2DDistanceSq(B, P);

	//calculate the point along AB that is the closest to P
	vector2D Point = A + ((B - A) * dotA)/(dotA + dotB);

	//calculate the distance P-Point
	return Vector2DDistanceSq(P,Point);
}


//--------------------LineIntersection2D-------------------------
//
//	Given 2 lines in 2D space AB, CD this returns true if an 
//	intersection occurs.
//
//----------------------------------------------------------------- 

inline bool LineIntersection2D(vector2D A,
							   vector2D B,
							   vector2D C, 
							   vector2D D)
{
	float rTop = (A.fY-C.fY)*(D.fX-C.fX)-(A.fX-C.fX)*(D.fY-C.fY);
	float sTop = (A.fY-C.fY)*(B.fX-A.fX)-(A.fX-C.fX)*(B.fY-A.fY);

	float Bot = (B.fX-A.fX)*(D.fY-C.fY)-(B.fY-A.fY)*(D.fX-C.fX);

	if (Bot == 0)//parallel
	{
		return false;
	}

	float invBot = 1.0f/Bot;
	float r = rTop * invBot;
	float s = sTop * invBot;

	if( (r > 0) && (r < 1) && (s > 0) && (s < 1) )
	{
		//lines intersect
		return true;
	}

	//lines do not intersect
	return false;
}

//--------------------LineIntersection2D-------------------------
//
//	Given 2 lines in 2D space AB, CD this returns true if an 
//	intersection occurs and sets dist to the distance the intersection
//  occurs along AB
//
//----------------------------------------------------------------- 

inline bool LineIntersection2D(vector2D A,
							   vector2D B,
							   vector2D C, 
							   vector2D D,
							   float &dist)
{

	float rTop = (A.fY-C.fY)*(D.fX-C.fX)-(A.fX-C.fX)*(D.fY-C.fY);
	float sTop = (A.fY-C.fY)*(B.fX-A.fX)-(A.fX-C.fX)*(B.fY-A.fY);

	float Bot = (B.fX-A.fX)*(D.fY-C.fY)-(B.fY-A.fY)*(D.fX-C.fX);


	if (Bot == 0)//parallel
	{
		if (FloatEquals(rTop, 0.0f) && FloatEquals(sTop, 0.0f))
		{
			return true;
		}
		return false;
	}

	float r = rTop/Bot;
	float s = sTop/Bot;

	if( (r > 0) && (r < 1) && (s > 0) && (s < 1) )
	{
		dist = Vector2DDistance(A,B) * r;

		return true;
	}

	else
	{
		dist = 0;

		return false;
	}
}

//-------------------- LineIntersection2D-------------------------
//
//	Given 2 lines in 2D space AB, CD this returns true if an 
//	intersection occurs and sets dist to the distance the intersection
//  occurs along AB. Also sets the 2d vector point to the point of
//  intersection
//----------------------------------------------------------------- 
inline bool LineIntersection2D(vector2D   A,
							   vector2D   B,
							   vector2D   C, 
							   vector2D   D,
							   float&     dist,
							   vector2D&  point)
{

	float rTop = (A.fY-C.fY)*(D.fX-C.fX)-(A.fX-C.fX)*(D.fY-C.fY);
	float rBot = (B.fX-A.fX)*(D.fY-C.fY)-(B.fY-A.fY)*(D.fX-C.fX);

	float sTop = (A.fY-C.fY)*(B.fX-A.fX)-(A.fX-C.fX)*(B.fY-A.fY);
	float sBot = (B.fX-A.fX)*(D.fY-C.fY)-(B.fY-A.fY)*(D.fX-C.fX);

	if ( (rBot == 0) || (sBot == 0))
	{
		//lines are parallel
		return false;
	}

	float r = rTop/rBot;
	float s = sTop/sBot;

	if( (r > 0) && (r < 1) && (s > 0) && (s < 1) )
	{
		dist = Vector2DDistance(A,B) * r;

		point = A + (B - A) * r ;

		return true;
	}

	else
	{
		dist = 0;

		return false;
	}
}


